import java.util.*;

/**
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 * 返回这三个数的和。
 *
 * 假定每组输入只存在恰好一个解。
 *
 */
public class Solution {

    public int threeSumClosest(int[] nums, int target) {
        if (nums.length == 3) {
            return nums[0] + nums[1] + nums[2];
        }

        //排序
        List<Integer> list = new ArrayList<>();
        for (int n : nums) {
            list.add(n);
        }
        Collections.sort(list);

        //第三列表 值为 -target
        List<Integer> thirdList = new ArrayList<>(list.size());
        for (int n : list) {
            thirdList.add(n - target);
        }

        int result = Integer.MAX_VALUE;
        int temp;
        //遍历
        for (int first = 0; first < list.size(); first++) {
            for (int second = first + 1; second < list.size() - 1; second++) {
                temp = list.get(first) + list.get(second);
                int findValue = findNear(thirdList, -temp, second + 1);
                result = nearZero(result, temp + findValue);
                if (result == 0) {
                    return target;
                }
            }
        }
        return result + target;
    }
    private static int findNear(List<Integer> list, int tar, int start) {
        int diff_per = Integer.MAX_VALUE;
        int diff;
        int mid;
        int end = list.size() - 1;

        while ((end - start) > 6) {
            mid = (start + end) / 2;
            if (list.get(mid) > tar) {
                end = mid;
            } else if (list.get(mid) < tar) {
                start = mid;
            } else {
                return list.get(mid);
            }
        }

        while (start <= end) {
            diff = Math.abs(tar - list.get(start));
            if (diff < diff_per) {
                diff_per = diff;
            } else {
                return list.get(start - 1);
            }
            start++;
        }
        return list.get(end);
    }

    private static int nearZero(int l, int r) {
        if (l < 0) {
            if (r < 0) {
                return l > r ? l : r;
            } else if (r > 0) {
                return -l > r ? r : l;
            } else {
                return 0;
            }
        } else if (l > 0) {
            if (r < 0) {
                return l > -r ? r : l;
            } else if (r > 0) {
                return l > r ? r : l;
            } else {
                return 0;
            }
        } else {
            return 0;
        }
    }

}